package tree;


//二叉搜索树，查找第k个的节点，实际上就是中序遍历，再加一个计数,第k大节点就是遍历的第k个元素
public class FIndK {

  private int index = 1;

  public IntTreeNode findK(IntTreeNode root, int k) {

    if (root == null || k <= 0) {
      return null;
    }
    IntTreeNode result = null;

    if (root.getLeft() != null) {
      result = findK(root.getLeft(), k);
    }
    //左子树没找到
    if (result == null) {
      if (index == k) {
        result = root;
        return result;
      } else {
        index++;
      }
    }

    if (result == null && root.getRight() != null) {
      result = findK(root.getRight(), k);
    }

    return result;
  }


  public static void main(String args[]) {
    IntTreeNode root = new IntTreeNode(10);
    root.setLeft(new IntTreeNode(6));
    root.getLeft().setLeft(new IntTreeNode(4));
    root.getLeft().setRight(new IntTreeNode(8));
    root.getLeft().getRight().setLeft(new IntTreeNode(7));
    root.getLeft().getRight().setRight(new IntTreeNode(9));
    root.setRight(new IntTreeNode(14));
    root.getRight().setLeft(new IntTreeNode(12));
    root.getRight().setRight(new IntTreeNode(16));

    FIndK fIndK = new FIndK();
    IntTreeNode result = fIndK.findK(root, 9);
    System.out.println(result.getValue());
  }
}
